Field of the Invention
The present invention relates to inference-based network route control. In particular, but not exclusively, the present invention relates to processing routes for modification of a routing definition, the routing definition being used by a network device to route network traffic in an electronic data network.
Description of the Related Technology
In a communications network, network devices are arranged and configured to control how information is transmitted across the network. For example, in a packet-switched network, one or more network devices such as routers, bridges, gateways, firewalls and switches may be arranged and/or configured to selectively forward packets across the network. A network device may use a routing definition such as a routing table that lists a number of routes or paths through the network to deliver a packet to a defined destination. These network devices may also be arranged to perform a number of control plane routing functions, such as filtering packets, discarding packets, or providing certain packets with preferential routing. A typical network device comprises an embedded computing device with a microcontroller arranged and configured to load computer program code in the form of firmware from a read-only or flash memory.
Large scale networks, such as the Internet, use a variety of routing protocols to determine how network traffic is to be routed through a large number of heterogeneous networks. These networks initially used static routing definitions. However, these quickly became impractical given the number of interconnected networks and the organic growth of connections. Hence, routing protocols such as Border Gateway Protocol (BGP) were developed. These routing protocols allow particular networks or routing domains, which are referred to in BGP as autonomous systems, to exchange routing information so as to agree upon a suitable path for routing network traffic. Typically, network devices within each autonomous system exchange network route definitions, e.g. proposed routes, and a routing policy is implemented by a given network device to determine which route definitions are to be added to the network device's working routing definition or table. For example, a router may receive several different proposed routes for routing network traffic, such as data packets, to a given destination. The router would thus implement a routing policy to determine which of the several different proposed routes to use. A routing policy may be applied to one or more route attributes that are defined as part of the received network route definitions. For example, one attribute is AS_PATH, i.e. a definition of the path through one or more autonomous systems that is associated with the route. If a proposed route passes through autonomous systems 1, 3 and 5 then the AS_PATH may be defined as {1, 3, 5}. Certain routing policies select a proposed route based on the AS_PATH length. In the aforementioned example the path length is 3, and this network route definition may be selected over a proposed route with a path length of 5.
While routing protocols such as BGP have been successful at managing with the growth of large scale networks such as the Internet there are a number of issues with their use.
A first issue is network security. If malicious parties hijack the exchange of network route definitions they may be able to suggest their own insecure routes over a number of more secure alternative routes. For example, a malicious party may hijack the exchange of network route definitions to perform surveillance, industrial espionage, or fraud. Man-in-the-middle attacks that operate on this basis, e.g. advertising a route through a malicious party's network devices in order to intercept network traffic, are becoming increasing common. They are also difficult to detect; the malicious party may continue to route the network traffic to its defined destination making it difficult for either the sender or the receiver to determine that the traffic has been intercepted. In 2013, attacks such as these were detected on at least 60 days of the year with over 1,500 individual Internet Protocol (IP) blocks being hijacked, with hijackers working in a number of different countries and hijacking events lasting from minutes to days.
A second issue is routing error. For example, if an incorrect or inefficient route is advertised, and it complies with the implemented routing policy (e.g. it provides a shorter path than comparative routes), it can quickly become the default route for large quantities of network traffic. For example, if a small organization managing a particular autonomous system erroneously or accidently advertisers a route through its networks for a popular Internet site, then these networks can be very rapidly overwhelmed by huge quantities of network traffic. This may not only take the network devices of the small organization offline, it may also take down the popular Internet site. On 24 Feb. 2008, YouTube® was taken offline for an hour as an error lead to worldwide network traffic for YouTube® being routed through a single country's servers, which were unable to cope with the network load. This was due to an incorrect route being advertised and propagating over the BGP control plane
Routes that are not necessarily erroneous but that are simply inefficient may also easily be added to the routing tables of hundreds if not millions of network devices. For example, if a routing policy is configured to select a shortest path, this may not always be the quickest path, e.g. a longer path may have faster physical connections or better bandwidth.
A third issue is the size of Internet. There are over 40,000 autonomous systems on the Internet and active BGP entries in a typical routing table have been rising exponentially. For example, the BGP Forwarding Table has over half a million active entries.
One approach to addressing these issues is to increase the complexity of routing policies. Certain network devices have routing policies that are implemented based on a number of “policy statements”. In these cases each policy statement can either accept, reject, or otherwise modify a proposed route, or let a following statement evaluate it. Boolean logic is applied on a complete set of policy statements. The final outcome of this process is either a rejection of the proposed route, or an acceptance with an optional modification of metadata associated with the route. Based on this approach, rules for adding a proposed route are arranged into complex Boolean decision trees. These are often difficult to update when new threats are uncovered and quickly become extremely complex. For example, certain existing BGP policy implementations have over half a million policy statements, with an expectation that these will continue to grow in size. As such, maintaining such policy statements is expensive, slow and prone to error. It also means that network operators are not able to respond to new threats on the timescales needed to mitigate them.
There is thus a desire to address the aforementioned issues in an efficient manner. For example, there is a desire to configure network devices such that security threats may be reduced while minimizing a risk of increased error and/or complexity.